﻿#define LBVH
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using RayDen.Library.Components.SystemComponents;
using RayDen.Library.Core;
using RayDen.Library.Core.Primitives;
using RayDen.Library.Entity.Scene;
using RayDen.RayEngine.Core.Interface;
using RayDen.RayEngine.Core.Types;
using RayDen.RayEngine.Data;
using Wintellect.PowerCollections;
namespace RayDen.RayEngine.IntersectionEngines
{
    using BaseRenderable = TriangleDataInfo;
    using RenderableCollection = List<TriangleDataInfo>;


    public struct BBox
    {
        public Point Min;
        public Point Max;

        public BBox(AABB b)
        {
            this.Max = b.Max;
            this.Min = b.Min;
        }

        public static bool IntersectBox(ref BBox box, RayInfo ray)
        {
            float t0 = ray.Min;
            float t1 = ray.Max;

            var rayInvDir = ray.InvDir;
            //1f /ray.Dir;

            float invDirX = rayInvDir.x;
            if (!process_box_coord(ref t0, ref t1, box.Min.x - ray.Org.x, box.Max.x - ray.Org.x, invDirX))
                return false;

            float invDirY = rayInvDir.y;
            if (!process_box_coord(ref t0, ref t1, box.Min.y - ray.Org.y, box.Max.y - ray.Org.y, invDirY))
                return false;

            float invDirZ = rayInvDir.z;
            if (!process_box_coord(ref t0, ref t1, box.Min.z - ray.Org.z, box.Max.z - ray.Org.z, invDirZ))
                return false;
            return true;
        }

        public static bool IntersectBox(BBox box, RayInfo ray)
        {
            float t0 = ray.Min;
            float t1 = ray.Max;

            var rayInvDir = ray.InvDir;
            //1f /ray.Dir;

            float invDirX = rayInvDir.x;
            if (!process_box_coord(ref t0, ref t1, box.Min.x - ray.Org.x, box.Max.x - ray.Org.x, invDirX))
                return false;

            float invDirY = rayInvDir.y;
            if (!process_box_coord(ref t0, ref t1, box.Min.y - ray.Org.y, box.Max.y - ray.Org.y, invDirY))
                return false;

            float invDirZ = rayInvDir.z;
            if (!process_box_coord(ref t0, ref t1, box.Min.z - ray.Org.z, box.Max.z - ray.Org.z, invDirZ))
                return false;
            return true;
        }

        private static bool process_box_coord(ref float t0, ref float t1, float mnRO, float mxRO, float invRayDir)
        {
            float tNear = (mnRO) * invRayDir;
            float tFar = (mxRO) * invRayDir;
            // Update parametric interval from slab intersection $t$s
            if (tNear > tFar)
                swap(ref tNear, ref tFar);
            t0 = tNear > t0 ? tNear : t0;
            t1 = tFar < t1 ? tFar : t1;
            if (t0 > t1)
                return false;
            return true;
        }
        private static void swap(ref float tNear, ref  float tFar)
        {
            float tmp = tNear;
            tNear = tFar;
            tFar = tmp;
        }
    }

    public class BottomUpBvhAccelleration
    {
        public int TraversalStackSize = 64;
        public const uint NoHit = 20000000;

        public Node RootNode;
        private int bvhNodesCount;


        public class Node
        {
            public Guid NodeId;
            public AABB Bound;
            public Node Left, Right;
            public List<TriangleDataInfo> Primitives;
            public uint PrimitiveIndexStart, Count;
            public Axis SplitAxis;
            public Node()
            {
                NodeId = Guid.NewGuid();
            }
        }

        [StructLayout(LayoutKind.Explicit, Size = 32)]
        public struct GLNode
        {
            [FieldOffset(0)]
            public BBox Bounds;
            [FieldOffset(24)]
            public uint SkipIndex;
            [FieldOffset(28)]
            public uint FirstOffset;
        }

        private Point[] sceneVertices;
        public TriangleDataInfo[] triangles;
        private List<ITriangleMesh> meshes;

        private List<GLNode> glNodes;

        public LNode[] nodes;


        private void LinearizeBVH()
        {
            nodes = new LNode[bvhNodesCount];
            //int offset = 0;

            this.BuildArray(RootNode, 0);

            glNodes = new List<GLNode>(nodes.Length);
            for (int i = 0; i < nodes.Length; i++)
            {
                var node = nodes[i];
                if (node.IsLeaf)
                {
                    glNodes.Add(new GLNode()
                    {
                        Bounds = node.Bounds,
                        FirstOffset = node.PrimitiveIndex
                    });
                }
                else
                {
                    glNodes.Add(new GLNode()
                    {
                        Bounds = node.Bounds,
                        FirstOffset = NoHit,
                        SkipIndex = node.SkipIndex
                    });

                }
            }
        }

        private int BuildArray(Node node, int offset)
        {
            var nd = node;
            LNode p;
            while (nd != null)
            {
                var firstOffset = offset;
                p = new LNode()
                {
                    Bounds = new BBox(nd.Bound),
                };
                offset = BuildArray(nd.Left, offset + 1);

                if (nd.PrimitiveIndexStart != NoHit)
                {
                    p.PrimitiveIndex = nd.PrimitiveIndexStart;
                    p.IsLeaf = true;
                }
                else
                {
                    p.Axis = (byte)nd.SplitAxis;
                    p.SkipIndex = (uint)offset;
                }

                nodes[firstOffset] = p;
                nd = nd.Right;
            }

            return offset;
        }


        public List<Node> BuildNodeLevel(IList<Node> prevLevel)
        {
            Node lnode, rnode;
            var result = new List<Node>();
            int index, leftOver;

            for (index = 0; index < prevLevel.Count - 1; index += 2)
            {
                lnode = prevLevel[index];
                rnode = prevLevel[index + 1];
                var bound = new AABB(lnode.Bound).Union(rnode.Bound);
                bvhNodesCount++;
                result.Add(new Node()
                {
                    Bound = bound,
                    SplitAxis = (Axis)bound.MaximumExtent(),
                    Left = lnode,
                    Right = rnode,
                    PrimitiveIndexStart = NoHit
                });

            }
            leftOver = prevLevel.Count - index;
            if (leftOver > 0)
            {
                //var leftNode = prevLevel[leftOver];
                Tracer.TraceLine("Left over nodes! {0} ", leftOver);
                var lNode = prevLevel.Last();
                result.Add(lNode);
                //bvhNodesCount++;
            }

            return result;
        }

        public void BuildBottomUpTree(List<TriangleDataInfo> primitives)
        {
            Tracer.TraceLine("Building Bottom Up accelleration .  {0} triangles", primitives.Count);
            AABB bound = primitives.Select(prim => prim.WorldBound(sceneVertices)).Aggregate((b1, b2) => b1.Union(b2));
            RootNode = new Node()
            {
                Bound = bound,
                PrimitiveIndexStart = NoHit
            };
            bvhNodesCount++;
            Tracer.TraceLine("Sorting primitives");
            primitives.Sort((a, b) => CompareTriangles(a, b, (Axis)bound.MaximumExtent()));

            List<Node> leafNodes = new List<Node>(primitives.Count);
            leafNodes.AddRange(primitives.Select((primitive, i) => new Node()
            {
                Bound = primitive.WorldBound(sceneVertices),
                Count = 1,
                PrimitiveIndexStart = (uint)i,
                Primitives = new RenderableCollection() { primitive }
            }));
            bvhNodesCount += leafNodes.Count;

            Tracer.TraceLine("{0} Leaf nodes", leafNodes.Count);
            List<Node> prevLevel = BuildNodeLevel(leafNodes).ToList();
            List<Node> nextLevelNodes = null;
            bool done = false;
            int level = 0;
            while (!done)
            {
                if (nextLevelNodes != null && nextLevelNodes.Count <= 2)
                {
                    done = true;
                }
                else
                {
                    nextLevelNodes = BuildNodeLevel(prevLevel);
                    prevLevel = nextLevelNodes;
                }

                level++;
            }
            Tracer.TraceLine("bvh max depth {0}", level);
            if (nextLevelNodes.Count == 1)
            {
                RootNode = nextLevelNodes[0];
            }
            else
            {
                RootNode.Left = nextLevelNodes[1];
                RootNode.Right = nextLevelNodes[0];
                //RootNode.Bound = nextLevelNodes[0].Bound.Union(nextLevelNodes[1].Bound);
            }
        }


        public void Init(RayEngineScene scene, ITriangleMesh[] geometry)
        {
            var sceneModel = scene;
            meshes = new List<ITriangleMesh>();
            meshes.AddRange(scene.Meshes);
            this.sceneVertices = sceneModel.Vertices;
            var trianglesCache = scene.Triangles.ToList();
            //Comparison<Triangle> tc = (t1, t2) => CompareTriangles(t1, t2, Axis.PLANE_Z);
            //trianglesCache.Sort(tc);
            //this.BuildTree(trianglesCache, 0, trianglesCache.Count-1);
            //this.triangles = trianglesCache.ToArray();

            this.BuildBottomUpTree(trianglesCache);
            this.triangles = trianglesCache.ToArray();

            Tracer.TraceLine("Linearize BVH");
            this.LinearizeBVH();
            Tracer.TraceLine("Complete");

            Tracer.TraceLine("Tree is builded, {0} nodes total", bvhNodesCount);
        }

        public int CompareTriangles(TriangleDataInfo t1, TriangleDataInfo t2, Axis a = Axis.PLANE_Y)
        {
            var p1 = t1.Center(sceneVertices);
            var p2 = t2.Center(sceneVertices);
            return p1.Component(a).CompareTo(p2.Component(a));
        }
        internal LNode[] GetData()
        {
            return this.nodes;
        }
        /*
        public bool Intersect(RayInfo ray, out IntersectionInfo intersection)
        {
#if LBVH
            intersection = new IntersectionInfo()
            {
                Distance = 1000000f
            };
            //return BVHAccel_Intersect(ray, ref intersection);
            return IntersectBVH(ray, ref intersection);
#else
            return IntersectNode(RootNode, ray, out intersection);
#endif
        }

        public bool Intersect(RayInfo ray)
        {
#if LBVH
            //return BVHAccel_SIntersect(ray);

            return this.ShadowIntersectBVH(ray);
#else
            return IntersectNode(RootNode, ray);
#endif
        }

        private bool IntersectNode(Node node, RayInfo ray, out IntersectionInfo intersection)
        {
            if (node == null)
            {
                intersection = null;
                return false;
            }
            float t0, t1 = 0f, dist = float.MaxValue, u = 0f, v = 0f;
            if (BVHAccellerationStructure.IntersectBox(node.Bound, ray))
            {
                //ray.MinT = t0;
                //ray.MaxT = t1;

                if (node.Primitives != null && node.Primitives.Count > 0)
                {
                    for (int i = 0; i < node.Primitives.Count; i++)
                    {
                        if (node.Primitives[i].Intersect(ref sceneVertices, ref ray, ref t1, ref u, ref v) && dist > t1)
                        {
                            var triangleMesh = node.Primitives[i].Owner;
                            intersection = new IntersectionInfo();
                            dist = t1;
                            intersection.Distance = dist;
                            intersection.Geometry = node.Primitives[i];
                            intersection.Point = ray.Point(dist);
                            intersection.Material = materialProvider.Get(triangleMesh.MaterialName);

                            var gnormal =
                                intersection.Geometry.InterpolateMeshNormal(u, v).Normalize();
                            //InterpolateNormal(ref sceneVertices, u, v).Normalize();
                            //triangleMesh.GetTriangleNormal(i, 0);
                            //triangleMesh.InterpolateTriangleNormal(i, u, v).Normalize();
                            Normal shadeN;

                            if (Vector.Dot(ref ray.Dir, ref gnormal) >= 0f)
                                shadeN = -gnormal;
                            else
                                shadeN = gnormal;

                            intersection.ShadingNormal = shadeN;
                            intersection.Normal = gnormal;
                            //                                    triangleMesh.InterpolateTriangleNormal(i, u, v);
                            //triangleMesh.triangles[i].InterpolateNormal(ref scene.Vertices, u, v).Normalize();
                            //triangleMesh.triangles[i].InterpolateNormal(ref scene.Vertices, u, v).Normalize();
                            //triangleMesh.triangles[i].ComputeNormal(ref scene.Vertices).Normalize();

                            intersection.TexCoords = new UV(u, v);
                            //triangleMesh.InterpolateTriUV(i, u, v);
                            return true;
                        }
                    }
                }

                IntersectionInfo li, ri;
                var leftIntersect = IntersectNode(node.Left, ray, out li);
                var rIntersect = IntersectNode(node.Right, ray, out ri);
                if (leftIntersect & rIntersect)
                {
                    intersection = li.Distance > ri.Distance ? ri : li;
                    return true;
                }
                if (leftIntersect)
                {
                    intersection = li;
                    return true;
                }
                if (rIntersect)
                {
                    intersection = ri;
                    return true;
                }

            }
            intersection = null;
            return false;
        }


        private bool IntersectNode(Node node, RayInfo ray)
        {
            if (node == null)
            {
                return false;
            }
            float t1 = 0f, u = 0f, v = 0f;
            if (BVHAccellerationStructure.IntersectBox(node.Bound, ray))
            {
                if (node.Primitives != null && node.Primitives.Count > 0)
                {
                    for (int i = 0; i < node.Primitives.Count; i++)
                    {
                        if (node.Primitives[i].Intersect(ref sceneVertices, ref ray, ref t1, ref u, ref v))
                        {
                            return true;
                        }
                    }
                }
                return IntersectNode(node.Left, ray) || IntersectNode(node.Right, ray);
            }
            return false;
        }



        private bool IntersectBVH(RayInfo ray, ref IntersectionInfo sp)
        {
            if (sp == null)
            {
                sp = new IntersectionInfo();
            }
            if (nodes.Length == 0)
                return false;
            TriangleMesh lastHitMesh = null;
            int lastHitIndex = -1, triangleIndex = -1;
            float u = 0f, v = 0f;
            bool hit = false;
            Vector invDir = ray.InvDir;
            //new Vector(1f / ray.Dir.x, 1f / ray.Dir.y, 1f / ray.Dir.z);
            var dirIsNeg = new[] { invDir.x < 0, invDir.y < 0, invDir.z < 0 };
            int todoOffset = 0, nodeNum = 0;
            int[] todo = new int[TraversalStackSize];
            var dist = float.MaxValue;
            while (true)
            {
                float t1 = 0f;
                if (BBox.IntersectBox(ref nodes[nodeNum].Bounds, ray))
                {
                    //if (node.bbox.Intersect(vray, out t0, out t2)) {
                    if (nodes[nodeNum].IsLeaf)//if (nodes[nodeNum].PrimitiveIndex != NoHit)
                    {
                        {
                            var triIdx = Math.Min(nodes[nodeNum].PrimitiveIndex, triangles.Length - 1);

                            if (triangles[triIdx].Intersect(ref sceneVertices, ref ray, ref t1, ref u, ref v))
                            {
                                if (dist > t1) //
                                {
                                    triangleIndex = (int)triIdx;
                                    lastHitMesh = triangles[triIdx].Owner;
                                    lastHitIndex = triangles[triIdx].Index;
                                    dist = t1;
                                    sp.Point = ray.Point(dist);
                                    sp.Geometry = triangles[triIdx];
                                    sp.Distance = dist;
                                    hit = true;
                                }
                            }
                        }
                        if (todoOffset == 0)
                            break;
                        nodeNum = todo[--todoOffset];
                    }
                    else
                    {
                        var axis = nodes[nodeNum].Axis;
                        if (dirIsNeg[axis])
                        {
                            todo[todoOffset++] = nodeNum + 1;
                            nodeNum = (int)nodes[nodeNum].SkipIndex;
                        }
                        else
                        {
                            todo[todoOffset++] = (int)nodes[nodeNum].SkipIndex;
                            nodeNum = nodeNum + 1;
                        }
                    }
                }
                else
                {
                    if (todoOffset == 0)
                        break;
                    nodeNum = todo[--todoOffset];
                }
            }

            if (hit)
            {
                sp.Material = materialProvider.Get(lastHitMesh.MaterialName);
                var gnormal = triangles[triangleIndex].InterpolateMeshNormal(u, v).Normalize();
                Normal shadeN;

                if (Vector.Dot(ref ray.Dir, ref gnormal) >= 0f)
                    shadeN = -gnormal;
                else
                    shadeN = gnormal;

                sp.ShadingNormal = shadeN;
                sp.Normal = gnormal;
                //triangles[node.primOffset + i].InterpolateNormal(ref sceneModel.Vertices, u, v).Normalize();
                sp.TexCoords = lastHitMesh.InterpolateTriUV(lastHitIndex, u, v);
                return true;
            }

            return false;
        }

        private bool ShadowIntersectBVH(RayInfo ray)
        {
            if (nodes.Length == 0)
                return false;
            bool hit = false;
            Vector invDir = ray.InvDir;
            //new Vector(1f / ray.Dir.x, 1f / ray.Dir.y, 1f / ray.Dir.z);
            var dirIsNeg = new[] { invDir.x < 0, invDir.y < 0, invDir.z < 0 };
            int todoOffset = 0, nodeNum = 0;
            int[] todo = new int[TraversalStackSize];
            while (true)
            {
                float t1 = 0f, u = 0f, v = 0f;
                if (BBox.IntersectBox(ref nodes[nodeNum].Bounds, ray))
                {
                    //if (nodes[nodeNum].PrimitiveIndex != NoHit)
                    if (nodes[nodeNum].IsLeaf)
                    {
                        //for (int i = 0; i < nodes[nodeNum].Count; i++)
                        {
                            var triIdx = Math.Min(nodes[nodeNum].PrimitiveIndex, triangles.Length - 1);
                            if (triangles[triIdx].Intersect(ref sceneVertices, ref ray, ref t1, ref u, ref v))
                            {
                                return true;
                            }
                        }
                        if (todoOffset == 0)
                            break;
                        nodeNum = todo[--todoOffset];
                    }
                    else
                    {
                        var axis = nodes[nodeNum].Axis;
                        if (dirIsNeg[axis])
                        {
                            todo[todoOffset++] = nodeNum + 1;
                            nodeNum = (int)nodes[nodeNum].SkipIndex;
                        }
                        else
                        {
                            todo[todoOffset++] = (int)nodes[nodeNum].SkipIndex;
                            nodeNum = nodeNum + 1;
                        }
                    }
                }
                else
                {
                    if (todoOffset == 0)
                        break;
                    nodeNum = todo[--todoOffset];
                }
            }

            return hit;
        }


        #region DADE INTERSECT

        private bool BVHAccel_Intersect(RayInfo ray, ref IntersectionInfo sp)
        {
            float u = 0f, v = 0f, t1 = 0f;
            int currentNode = 0; // Root Node
            int stopNode = (int)glNodes[0].SkipIndex;// nodes.Length; // Non-existent
            bool hit = false;
            TriangleMesh lastHitMesh = null;
            int lastHitIndex = -1, triangleIndex = -1;
            while (currentNode < stopNode)
            {
                var bbox = glNodes[currentNode].Bounds;
                if (BBox.IntersectBox(ref bbox, ray))
                {
                    if (glNodes[currentNode].FirstOffset != NoHit)
                    {
                        //for (int i = 0; i <= glNodes[currentNode].Count; i++)
                        {
                            if (triangles[glNodes[currentNode].FirstOffset].Intersect(ref sceneVertices, ref ray, ref t1, ref u, ref v))
                            {
                                if (t1 < sp.Distance)
                                {
                                    hit = true; // Continue testing for closer intersections

                                    sp.Point = ray.Point(t1);
                                    sp.Geometry = triangles[glNodes[currentNode].FirstOffset];
                                    sp.Distance = t1;
                                    triangleIndex = (int)glNodes[currentNode].FirstOffset;
                                    lastHitMesh = triangles[glNodes[currentNode].FirstOffset].Owner;
                                    lastHitIndex = triangles[glNodes[currentNode].FirstOffset].Index;
                                }
                            }
                        }
                    }
                    currentNode++;
                }
                else
                    currentNode = (int)glNodes[currentNode].SkipIndex;
            }

            if (hit)
            {
                sp.Material = materialProvider.Get(lastHitMesh.MaterialName);
                var gnormal = triangles[triangleIndex].InterpolateMeshNormal(u, v).Normalize();
                Normal shadeN;

                if (Vector.Dot(ref ray.Dir, ref gnormal) >= 0f)
                    shadeN = -gnormal;
                else
                    shadeN = gnormal;

                sp.ShadingNormal = shadeN;
                sp.Normal = gnormal;
                //triangles[node.primOffset + i].InterpolateNormal(ref sceneModel.Vertices, u, v).Normalize();
                sp.TexCoords = lastHitMesh.InterpolateTriUV(lastHitIndex, u, v);
                return true;
            }

            return hit;
        }
        private bool BVHAccel_SIntersect(RayInfo ray)
        {
            float u = 0f, v = 0f, t1 = 0f;
            int currentNode = 0; // Root Node
            int stopNode = (int)glNodes[0].SkipIndex;// nodes.Length; // Non-existent
            while (currentNode < stopNode)
            {
                if (BBox.IntersectBox(glNodes[currentNode].Bounds, ray))
                {
                    if (glNodes[currentNode].FirstOffset != NoHit)
                    {
                        {
                            if (triangles[glNodes[currentNode].FirstOffset].Intersect(ref sceneVertices, ref ray,
                                                                                           ref t1, ref u, ref v))
                            {
                                return true;
                            }
                        }
                    }
                    currentNode++;
                }
                else
                    currentNode = (int)glNodes[currentNode].SkipIndex;
            }
            return false;

        }

        #endregion
        */
    }


}
